package com.example.demo.leetcode.classics150;

import java.util.*;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _100单词搜索II
 * @description
 * @date 2023/08/10 14:18
 * <p>
 * ******************************************************
 */
public class _100单词搜索II {


    /**
     * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。
     * <p>
     * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     * 同一个单元格内的字母在一个单词中不允许被重复使用。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
     * words = ["oath","pea","eat","rain"]
     * 输出：["eat","oath"]
     * 示例 2：
     * <p>
     * <p>
     * 输入：board = [["a","b"],["c","d"]], words = ["abcb"]
     * 输出：[]
     * <p>
     * <p>
     * 提示：
     * <p>
     * m == board.length
     * n == board[i].length
     * 1 <= m, n <= 12
     * board[i][j] 是一个小写英文字母
     * 1 <= words.length <= 3 * 104
     * 1 <= words[i].length <= 10
     * words[i] 由小写英文字母组成
     * words 中的所有字符串互不相同
     *
     * @param board
     * @param words
     * @return
     */
    /*public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (String word : words) {
                    if (!result.contains(word) && board[i][j] == word.charAt(0)) {
                        mark.put(word, false);
                        StringBuilder strace = new StringBuilder();
                        LinkedList<String> straceList = new LinkedList<>();
                        findWord(board, i, j, word, strace, straceList);
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }

    Set<String> result = new HashSet<>();
    Map<String, Boolean> mark = new HashMap<>();

    int[][] helper = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};


    private void findWord(char[][] board, int i, int j, String word, StringBuilder strace, LinkedList<String> straceList) {
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || mark.get(word)) {
            return;
        }
        strace.append(board[i][j]);
        straceList.add(i + "," + j);
        if (word.equals(strace.toString())) {
            mark.put(word, true);
            result.add(word);
            return;
        }
        if (word.charAt(strace.length() - 1) == (strace.charAt(strace.length() - 1))) {
            for (int[] item : helper) {
                if (!straceList.contains((i + item[0]) + "," + (j + item[1]))) {
                    findWord(board, i + item[0], j + item[1], word, strace, straceList);
                }
            }
        }
        strace.deleteCharAt(strace.length() - 1);
        straceList.removeLast();
    }*/


    public static void main(String[] args) {
        _100单词搜索II s = new _100单词搜索II();
        System.out.println(s.findWords(new char[][]{{'a', 'a'}}, new String[]{"aaa"}));
    }




    //改造前缀树节点
    class TrieNode {
        public TrieNode[] children;
        public String word; //节点直接存当前的单词

        public TrieNode() {
            children = new TrieNode[26];
            word = null;
            for (int i = 0; i < 26; i++) {
                children[i] = null;
            }
        }
    }

    class Trie {
        TrieNode root;

        /**
         * Initialize your data structure here.
         */
        public Trie() {
            root = new TrieNode();
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            char[] array = word.toCharArray();
            TrieNode cur = root;
            for (int i = 0; i < array.length; i++) {
                // 当前孩子是否存在
                if (cur.children[array[i] - 'a'] == null) {
                    cur.children[array[i] - 'a'] = new TrieNode();
                }
                cur = cur.children[array[i] - 'a'];
            }
            // 当前节点结束，存入当前单词
            cur.word = word;
        }
    }


//    class Solution {
        public List<String> findWords(char[][] board, String[] words) {
            Trie trie = new Trie();
            //将所有单词存入前缀树中
            List<String> res = new ArrayList<>();
            for (String word : words) {
                trie.insert(word);
            }
            int rows = board.length;
            if (rows == 0) {
                return res;
            }
            int cols = board[0].length;
            //从每个位置开始遍历
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    existRecursive(board, i, j, trie.root, res);
                }
            }
            return res;
        }

        private void existRecursive(char[][] board, int row, int col, TrieNode node, List<String> res) {
            if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
                return;
            }
            char cur = board[row][col];//将要遍历的字母
            //当前节点遍历过或者将要遍历的字母在前缀树中不存在
            if (cur == '$' || node.children[cur - 'a'] == null) {
                return;
            }
            node = node.children[cur - 'a'];
            //判断当前节点是否是一个单词的结束
            if (node.word != null) {
                //加入到结果中
                res.add(node.word);
                //将当前单词置为 null，防止重复加入
                node.word = null;
            }
            char temp = board[row][col];
            //上下左右去遍历
            board[row][col] = '$';
            existRecursive(board, row - 1, col, node, res);
            existRecursive(board, row + 1, col, node, res);
            existRecursive(board, row, col - 1, node, res);
            existRecursive(board, row, col + 1, node, res);
            board[row][col] = temp;
        }
//    }


}





